package leetcode_1_20;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class isValid_20 {
    /**
     * 有效的括号
     * 有效字符串需满足：
     * 左括号必须用相同类型的右括号闭合。
     * 两层for循环，在int数组中用0和1判断是否所有字符满足，速度太慢
     * [ ] { { } [ ] }
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        Map<Character,Character>map=new HashMap<>();
        map.put('(',')');
        map.put('{','}');
        map.put('[',']');
        if(s.length() % 2 != 0)
            return false;
        int len=s.length(),last = 10000,count=1;
        int [] result=new int[len];
         for(int i=0;  i < len ;i++){
             if(result[i] == 1) continue;    //右括号就不必再处理
             if(result[i] == 0 && map.get(s.charAt(i))==null ) return false;  //如果有单独存在的右括号直接返回false
             if(last <= i )                        //如果last<= i，说明上一个括号的范围已经结束
                 last=10000;
             for(int t = i + 1; t < len ;t++){     //如果已经遍历到前面括号的边界，说明该左括号没有匹配的字符
                 if(t > last)
                     return false;
                 if(s.charAt(i) == s.charAt(t) ) {                      //如果出现重复左括号
                     count++;
                 }
                 if(map.get(s.charAt(i)) == s.charAt(t) ){       //出现与其对应的第一个匹配括号
                     if(count !=1 ){
                         count--;
                         continue;
                     }
                     result[i]=1;
                     result[t]=1;
                     last=t;
                     break;
                 }
            }
         }
        for (int i:result) if(i==0) return false;
         return true;
    }

    /**
     * 逻辑最简单的方式
     * 调用replace库函数
     * @param s
     * @return
     */
    public boolean isValid2(String s) {
        int length = s.length() / 2;
        for (int i = 0; i < length; i++) {
            s = s.replace("()", "").replace("{}", "").replace("[]", "");
        }
        return s.length() == 0;
    }

    /**
     * 采用栈操作
     * 速度很快
     * @param s
     * @return
     */
    public static boolean isValid3(String s) {
        if(s.isEmpty())
            return true;
        Stack<Character> stack=new Stack<Character>();
        for(char c:s.toCharArray()){          //[ ] { { } [ ] }
            if(c=='(')
                stack.push(')');
            else if(c=='{')
                stack.push('}');
            else if(c=='[')
                stack.push(']');
            else if(stack.empty()||c!=stack.pop())
                //如果下个右括号与最近的左括号即栈顶元素无法对应
                //直接返回false
                return false;
        }
        if(stack.empty())
            return true;
        return false;
    }

}
